1. Field of the Invention
The present invention relates to an apparatus and method for displaying graphic information. More specifically, the present invention relates to an apparatus for determining whether a multi-dimensional object requires clipping before being displayed on a two-dimensional screen and a method for performing such determination.
2. Art Related to the Invention
Over the last few years, a variety of computer graphic systems have been developed for generating and displaying two and three dimensional objects on a two-dimensional display screen (e.g., a cathode ray tube "CRT"), liquid crystal display ("LCD") and the like). These computer-generated objects may represent tangible or conceptual objects to assist the user in visualizing the object and analyzing various conditions such as, for example, aerodynamic forces exerted on a certain design of an aircraft wing, structural integrity of a new architectural structure and the like. In these and other instances, it is easier, safer and more cost effective to conduct experiments on these objects than building and testing prototypes.
To display an object onto a display screen, the computer system undergoes numerous operations. One such operation is performing a clip check to determine if any portions of the object are positioned outside a clipping region (i.e., clipping window) and thereby obscured from view. Currently, there exist a number of conventional clip checking techniques that have been developed. One of these techniques uses an encoded binary representation (i.e., an "outcode") to indicate a particular location of a desired point (i.e., a vertex) of the object to be displayed. See James D. Foley, Andries van Dam, Steven K. Feiner and John F. Hughes, Computer Graphics Principles and Practice, Second Edition (Pages 111-124 and 271-278) incorporated herein by reference.
The purpose of using outcodes is to rapidly determine whether an object is within the clipping window by calculating the outcode for each point of the object and thereafter, successively performing logical operations to determine a clip status for the entire object. The object is "trivially rejected" and is not displayed on a display screen of the computer if the object lies completely outside the clipping window. In contrast, the object is "trivially accepted" and displayed in its entirety if it lies completely within the clipping window. If the object is not "trivially rejected" or "trivially accepted", further analysis is required. This further analysis determines whether the object is outside the clipping window or is partially visible.
For example, in a two-dimensional case, a clipping window 1 is defined by four planar boundary constraints at X.sub.min, X.sub.max, Y.sub.min and Y.sub.max 2-5 as shown in FIG. 1a. In this example, four objects labeled A,B,C and D 6-9 are illustrated in which object A 6 is "trivially accepted" and object B 7 is "trivially rejected". In addition, objects C 8 and object D 9 require further analysis to determine whether the particular object is outside the clipping window (e.g., object C 8 ) or partially visible (e.g., object D 9).
Conventionally, as listed on Page 116 and inferred on Page 276 of Computer Graphics Principles and Practice, numerous conditional branches are used in determining outcodes used for clip checking. These conditional branches and comparisons are required to determine whether each point having two coordinates (X,Y) for a two-dimensional object or three coordinates (X,Y,Z) and a normalizing coordinate (W) for a three dimensional object is within the clipping window. The conventional process used to determine outcodes for points forming an object to be displayed is shown in pseudo-code in Table 1 below. Explicit constants as Arabic numbers are used rather than bit representations for the sake of clarity.
TABLE 1 ______________________________________ Conventional Two-Dimensional Outcode Algorithm ______________________________________ /* Operator Definitions */ /* (".vertline.") is a logical OR */ /* ("&") is a logical AND */ Outcode = "0"; if (X &lt; X.sub.min), then Outcode = (Outcode .vertline. "1"); if (X &gt; X.sub.max), then Outcode = (Outcode .vertline. "2"); if (Y &lt; Y.sub.min), then Outcode = (Outcode .vertline. "4"); if (Y &gt; Y.sub.max), then Outcode = (Outcode .vertline. "8"); ______________________________________
The conventional method for formulating outcodes for clip checking of three-dimensional objects is shown as pseudo-code in Table 2, wherein the method is generally similar in operation to the conventional two-dimensional process. The coordinate system is preferably in homogeneous coordinates (i.e., dividing X, Y, and Z coordinates by a normalizing coordinate (W) for efficiency reasons. As shown in FIGS. 1b-1d, a three-dimensional homogeneous clipping window 10 is defined by six planar boundary constraints at -1.ltoreq.X/W.ltoreq.1, -1.ltoreq.Y/W&lt;1 and -1.ltoreq.Z/W.ltoreq.1, excluding the invalid case where X=0, Y=0, Z=0 and W=0. These outcodes for three dimensional objects are generally represented by six bits being a concatenation of two bits associated with each three dimensional coordinate (X, Y, Z).
TABLE 2 ______________________________________ Conventional Three-Dimensional Outcode Algorithm ______________________________________ /* Initialize the byte representing the Outcode */ Outcode = "0"; /* activate first or second bit of the Outcode */ if (ABS(X) &gt; W) if (X &lt; 0), Outcode = (Outcode .vertline. "2"); else Outcode = (Outcode .vertline. "1"); /* activate third or fourth bit of the Outcode */ if (ABS(Y) &gt; W) if (Y &lt; 0), Outcode = (Outcode .vertline. "8"); else Outcode = (Outcode .vertline. "4"); /* activate fifth or sixth bit of the Outcode */ if (ABS(Z) &gt; W) if (Z &lt; 0), Outcode = (Outcode .vertline. "32"); else Outcode = (Outcode .vertline. "16"); ______________________________________
Thereafter, to determine whether an object formed by a number of points is completely within the clipping window ("trivial accept"), or completely outside the clipping window ("trivial reject"), logical operations are applied to the outcode of those points. The object is trivially accepted if the outcodes of each of the points are logically OR'ed (i.e., a bit-by-bit OR) together to form a resultant outcode and every bit of the resultant outcode is equal to "zero". However, the object is trivially rejected if the outcodes of the points are bit-by-bit logically AND'ed together to form a resultant outcode and any bit of the resultant outcode is "non-zero". Otherwise, further analysis is needed.
In typical applications, nearly all of the objects displayed will be trivially rejected or accepted. The number of objects that require further analysis is usually in the range of 1%-10% of the objects displayed. Thus, maximizing the performance of the trivial accept and reject stages are of utmost importance in maximizing the performance of the entire display process. Unfortunately, there exist a number of disadvantages associated with the conventional clip checking scheme.
One disadvantage is that a software implementation of the conventional clip checking mechanism operates at an extremely slow rate, thereby failing to optimally utilize high processing speeds of current and next generation processors. This slow rate is due to the use of Boolean conditional branch instructions. Hence, it would be desirous to develop a new clip checking scheme using an outcode representation but eliminating Boolean conditional branch instructions so as to enhance clip checking and overall display performance.
A second disadvantage is that the conventional clip checking mechanism relies on a floating point unit within the processor of the computer system to perform coordinate transformations on the object as well as to calculate its outcode value in a concurrent fashion. The floating point unit is implemented to be responsible for transformations and clip checking operations because previously, the delay caused by the floating point unit was merely a small percentage of the total time delay in displaying an object on a display device. Thus, any inefficiency with respect to the clip checking scheme had negligible effect on the computer system's performance. However, with the advent of faster processors and more advanced graphic hardware, the clip checking causes a greater percentage of the total time delay and has a more pronounced effect on the overall performance of the computer system. Hence, it would be desirous to interleave the transformation operations and the outcode calculations in order to improve overall system performance.